package commonusealgorithm;

import java.awt.*;
import java.util.ArrayList;

/**
 * @Author PoX21s
 * @Date: 2021/11/4 11:57
 * @Version 1.0
 */

public class Horse {
    static int X;
    static int Y;
    static boolean[] isVisited;
    static boolean finished;

    public static void main(String[] args) {
        X = 6;
        Y = 6;
        int[][] chessBoard = new int[X][Y];
        isVisited = new boolean[X * Y];
        int step = 1;

        long start = System.currentTimeMillis();

        traversalChessboard(chessBoard,1,1,step);

        long end = System.currentTimeMillis();

        System.out.println(end - start + "毫秒");

        for (int[] ints : chessBoard) {
            for (int i = 0; i < ints.length; i++) {
                System.out.printf("%3d",ints[i]);
            }
            System.out.println();
        }
    }

    /*
     * 思路
     * - 设置当前位置已经访问过
     * - 找出当前位置下一步能够行走的所有情况，存储在一个list中
     * - 将list中的第一种情况取出，判断能走的下一步能否行走
     *      - 如果可以则递归
     *      - 不能则在while循环中取出list中的下一种情况，直到list为空跳出循环
     * - 递归结束条件，如果棋盘中的每一个棋格都走过，则说明成功
     * - 否则继续递归判断
     *
     * */
    public static void traversalChessboard(int[][] chessBoard, int row, int column, int step){
        chessBoard[row][column] = step;
        isVisited[row * X + column] = true;

        ArrayList<Point> ps = nextArr(new Point(column, row));
        /*
        * 优化
        * - 将所有能够到达的情况进行，排序
        *   - 排序的规则是：
        *       - 能够在棋盘上行走距离最少的在前面
        * */
        ps.sort(((o1, o2) -> {
            return nextArr(o1).size() - nextArr(o2).size();
        }));

        while (!ps.isEmpty()){
            Point point = ps.remove(0);
            if (!isVisited[point.y * X + point.x]){
                traversalChessboard(chessBoard,point.y,point.x,++step);
            }
        }

        if (step < X * Y && !finished){
            chessBoard[row][column] = 0;
            isVisited[row * X + column] = false;
        } else {
            finished = true;
        }
    }

    public static ArrayList<Point> nextArr(Point curPoint){
        ArrayList<Point> ps = new ArrayList<Point>();
        //创建一个
        Point p1 = new Point();
        //表示马儿可以走 5 这个位置
        if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走 6 这个位置
        if((p1.x = curPoint.x - 1) >=0 && (p1.y=curPoint.y-2)>=0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走 7 这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走 0 这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走 1 这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走 2 这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走 3 这个位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走 4 这个位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

    public static void sort(ArrayList<Point> ps){
        ps.sort((o1,o2) -> {
            return nextArr(o1).size() - nextArr(o2).size();
        });
    }

}


/*        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                int num1 = nextArr(o1).size();
                int num2 = nextArr(o2).size();
                if (num1 < num2){
                    return -1;
                } else if (num1 == num2){
                    return  0;
                } else {
                    return 1;
                }
            }
        });*/